package com.zhugang.week04;

/**
 * @program algorithms
 * @description: mergeSort
 * @author: chanzhugang
 * @create: 2022/06/16 17:10
 */
public class MergeSort {

    /**
     * 归并排序
     * 时间复杂度：O(n), 画递归树分析
     *
     * @param a
     * @param n
     */
    public void mergeSort(int[] a, int n) {
        // 把大数组从中间分成两个有序小数组； 合并两个有序小数组
        mergeSort_r(a, 0, n - 1);
    }

    private void mergeSort_r(int[] a, int p, int r) {
        if (p >= r) {
            return;
        }
        int q = p + (r - p) / 2;
        // 递归拆分
        mergeSort_r(a, p, q);
        mergeSort_r(a, q + 1, r);

        // 合并两个有序数组
        merge(a, p, q, r);
    }

    private void merge(int[] a, int p, int q, int r) {
        // 合并两个有序数组成一个大数组（有序）:双指针法
        int i = p;
        int j = q + 1;
        int[] temp = new int[r - p + 1];
        int k = 0;
        while (i <= q && j <= r) {
            if (a[i] <= a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
            }
        }
        while (i <= q) {
            temp[k++] = a[i++];
        }
        while (j <= r) {
            temp[k++] = a[j++];
        }
        // 临时数组拷贝到原数组
        for (int l = 0; l <= r - p; l++) {
            a[p + l] = temp[l];
        }
    }

}